|
In graph theory, a star ''S''k is the complete bipartite graph ''K''1,''k'': a tree with one internal node and ''k'' leaves (but, no internal nodes and ''k'' + 1 leaves when ''k'' ≤ 1). Alternatively, some authors define ''S''k to be the tree of order ''k'' with maximum diameter 2; in which case a star of ''k'' > 2 has ''k'' − 1 leaves. A star with 3 edges is called a claw. The star ''S''k is edge-graceful when ''k'' is even and not when ''k'' is odd. It is an edge-transitive matchstick graph, and has diameter 2 (when ''k'' > 1), girth ∞ (it has no cycles), chromatic index ''k'', and chromatic number 2 (when ''k'' > 0). Additionally, the star has large automorphism group, namely, the symmetric group on k letters. Stars may also be described as the only connected graphs in which at most one vertex has degree greater than one. ==Relation to other graph families== Claws are notable in the definition of claw-free graphs, graphs that do not have any claw as an induced subgraph.〔.〕〔.〕 They are also one of the exceptional cases of the Whitney graph isomorphism theorem: in general, graphs with isomorphic line graphs are themselves isomorphic, with the exception of the claw and the triangle ''K''3.〔.〕 A star is a special kind of tree. As with any tree, stars may be encoded by a Prüfer sequence; the Prüfer sequence for a star ''K''1,''k'' consists of ''k'' − 1 copies of the center vertex.〔.〕 Several graph invariants are defined in terms of stars. Star arboricity is the minimum number of forests that a graph can be partitioned into such that each tree in each forest is a star, and the star chromatic number of a graph is the minimum number of colors needed to color its vertices in such a way that every two color classes together form a subgraph in which all connected components are stars.〔.〕 The graphs of branchwidth 1 are exactly the graphs in which each connected component is a star.〔.〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Star (graph theory)」の詳細全文を読む スポンサード リンク
|